package com.learn.algorithm.heap;

import com.learn.algorithm.list.ListNode;

import java.util.*;

public class HeapSortApply {

    public static ListNode mergeKLists(List<ListNode> heads) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);

        for (ListNode head : heads) {
            if (head != null) {
                heap.add(head);
            }
        }

        if (heap.isEmpty()) {
            return null;
        }

        ListNode head = heap.poll();
        ListNode current = head;
        while (!heap.isEmpty()) {
            if (current != null) {
                if (current.next != null) {
                    heap.add(current.next);
                }
                current.next = heap.poll();
                current = current.next;
            }
        }

        return head;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(0);
        ListNode h2 = new ListNode(2);
        ListNode h4 = new ListNode(4);
        ListNode h6 = new ListNode(6);
        head1.next = h2;
        h2.next = h4;
        h4.next = h6;

        ListNode head2 = new ListNode(1);
        ListNode h3 = new ListNode(3);
        ListNode h5 = new ListNode(5);
        ListNode h7 = new ListNode(7);
        head2.next = h3;
        h3.next = h5;
        h5.next = h7;
        List<ListNode> heads = new ArrayList<>();
        heads.add(head1);
        heads.add(head2);
        ListNode head = mergeKLists(heads);
        if (head != null) {
            head.print();
        }
    }
}
